The present invention relates generally to packet switching networks employed in multi-processor and parallel computer systems, and digital communications systems, and the like, and more particularly to packet switching nodes which employ a multiport memory and control logic coupled thereto which is employed to store and forward data packets to a plurality of output ports and which reduces output port contention among data packets arriving at the same input port.
One developing area of computer technology involves the design and development of large-scale, multi-processor-based distributed and parallel computer systems. Typical of these classes of computer systems and architectural approaches are the single instruction stream, multiple data stream (SIMD) computer architecture and the mutiple instruction stream, multiple data stream (MIMD) computer architecture.
A SIMD computer typically comprises a control unit, N processors, N memory modules and an interconnection network. The control unit broadcasts instructions to all of the processors, and all active processors execute the same instruction at the same time. Each active processor executes the instruction on data in its own associated memory module. The interconnection network provides a communications facility for the processors and memory modules.
A MIMD computer typically comprises N processors and N memories, and each processor can execute an independent instruction stream. Each of the processors may communicate to any other processor. Similar interconnection networks may be employed in the MIMD computer.
Various interconnection networks may be employed to interconnect processors and memories employed in either type of computer system. These interconnection networks include delta networks, omega networks, indirect binary n-cube networks, flip networks, cube networks and banyan networks, for example.
The above-cited networks are discused in some detail in the following publications: "LSI implementation of modular interconnection networks for MIMD machines," 1980 Int'l. Conf. Parallel Processing, Aug. 1980, pp. 161-162; "Analysis and simulation of buffered delta networks," IEEE Trans. Computers, Vol. C-30, pp. 273-282, April 1981; "Processor-memory interconnections for multiprocessors," 6th Annual Int'l. Symp. Computer Architecture, April 1979, pp. 168-177; "Design and implementation of the banyan interconnection network in TRAC," AFIPS 1980 Nat'l. Computer Conf., June 1980, pp. 643-653; "The multistage cube: a versatile interconnection network," Computer, Vol. 14, pp. 65-76, Dec. 1981; "The hybrid cube network," Distributed Data Acquisition, Computing and Control Symp., Dec. 1980, pp. 11-22; and "Performance and implementation of 4.times.4 switching nodes in an interconnection network for PASM," 1981 Int'l Conf. on Parallel Processing, Aug. 1981, pp. 229-233.
Several types of data switching techniques may be employed to transfer data in SIMD and MIMD computers, and the like, including packet switching, message switching, time-division circuit switching or space-division circuit switching. Packet switching involves sending one or more words of data at a time through the system.
Conventional packet switching interconnection networks and nodes have a well-known problem involving the speed of transmission of information through the network. Conventional designs have typically employed a single queue coupled to each input port of the network to store and forward signal packets to all the output ports. In the single queue system, a contention problem occurs due to the fact that a signal packet destined for output port 2, for example, is blocked from exiting through that port because a signal packet destined for output port 1 is physically ahead of it in the queue and has not yet exited through port 1. This contention problem causes unnecessary transport delays and thus reduces system throughput.
One packet switching node which attempts to overcome this problem is described in a presently copending patent application entitled "Packet switched multiple queue N.times.M switch node," invented by R. J. McMillen and assigned to the assignee of the present invention. This invention utilizes a plurality of queue sets individually connected to each of the input ports in order to sort the signal packets according to output port destination. However, although this node improves the communications capability of computer systems employing it, it requires a large buffering capacity. This implies the use of a large number of storage transistors in the logic circuitry.